/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-28
 * Time: 14:01
 */
class Solution12 {
    public int numTrees(int n) {
        int[] dp = new int[n+1];

        //空树 或者 有意义
        dp[0] = 1;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}